import javafx.util.Pair;

/**
 * 给定一棵二叉树 root，返回所有重复的子树。
 *
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-duplicate-subtrees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class FindDuplicateSubtrees {
    /**
     * 法一：使用序列化进行唯一表示
     * 将二叉树序列化，然后将每颗子树序列化的结果存在map中，如果有两个相同的序列化结果，说明这是重复的子树
     */
//    Map<String,TreeNode> map=new HashMap<>();
//    Set<TreeNode> ans=new HashSet<>();
//    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
//        dfs(root);
//        return new ArrayList<TreeNode>(ans);
//    }
//    public String dfs(TreeNode root) {
//        if(root==null) {
//            return "";
//        }
//        StringBuilder str=new StringBuilder();
//        str.append(root.val);
//        str.append("(");
//        str.append(dfs(root.left));
//        str.append(")(");
//        str.append(dfs(root.right));
//        str.append(")");
//        String s=str.toString();
//        if(map.containsKey(s)) {
//            ans.add(map.get(s));
//        } else {
//            map.put(s,root);
//        }
//        return s;
//    }
    /**
     * 法二：优化版，采用三元组进行唯一表示
     */
    Map<String,Pair<TreeNode,Integer>> map=new HashMap<>();
    Set<TreeNode> ans=new HashSet<>();
    int idx=0;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return new ArrayList<TreeNode>(ans);
    }
    public int dfs(TreeNode root) {
        if(root==null) {
            return 0;
        }
        int[] til={root.val,dfs(root.left),dfs(root.right)};
        String hash=Arrays.toString(til);
        if(map.containsKey(hash)) {
            Pair<TreeNode,Integer> pair=map.get(hash);
            ans.add(pair.getKey());
            return pair.getValue();
        } else {
            map.put(hash,new Pair<TreeNode,Integer>(root,++idx));
            return idx;
        }
    }
}